package com.yoshino.leetcode.improve40.twentyforth;

import java.util.Random;

class Solution {

    // 前缀和 + 二分查找
    // 使用随机数，选取值为 1 ~ 权重和， 找到第一个前缀和 大于该 随机数的 前一个下标
    int sum;
    int[] pre;

    public Solution(int[] w) {
        // 前缀和
        pre = new int[w.length];
        pre[0] = w[0];
        for (int i = 1; i < w.length; i++) {
            pre[i] = pre[i - 1] + w[i];
        }
        sum = pre[w.length - 1];
    }

    public int pickIndex() {
        Random random = new Random();
        int ind = random.nextInt(sum) + 1;
        int left = 0, right = pre.length - 1, mid;
        while (left < right) {
            mid = left + ((right - left) >> 1);
            if (pre[mid] >= ind) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return right;
    }

    // 二分查找，使用 平方 判断
    public int mySqrt(int x) {
        int left = 0, right = x, mid, res = 0;
        while (left <= right) {
            mid = left + ((right - left) >> 1);
            if ((long) mid * mid == x) {
                return mid;
            }
            if ((long) mid * mid < x) {
                // 死循环的情况： left = mid
                left = mid + 1;
                res = mid;
            } else {
                right = mid - 1;
            }
        }
        return res;
    }

    public int minEatingSpeed(int[] piles, int h) {
        int max = piles[0];
        for (int i = 1; i < piles.length; i++) {
            max = Math.max(max, piles[i]);
        }
        int left = 0, right = max, mid;
        while (left <= right) {
            int th = 0;
            mid = left + ((right - left) >> 1);
            if (mid == 0) {
                return 1;
            }
            for (int pile : piles) {
                th += (pile - 1) / mid + 1;
            }
            if (th > h) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(w);
 * int param_1 = obj.pickIndex();
 */
